<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>Графы (easy)</h2>
<ol>
  <li>Хранение графов</li>
  <ol>
    <li>Списки смежности</li>
    <li>Списки ребер</li>
    <li>Добавление ребра в ориентированный граф за O(1)</li>
    <li>Удаление какого-нибудь ребра из ориентированного графа за O(1) (простой случай)</li>
    <li>Удаление заданного ребра из ориентированного графа за O(1) (хеш-таблица)</li>
  </ol></li>
  <li>DFS, BFS, 0-k BFS</li>
  <ol>
    <li>Найти путь между двумя вершинами за O(E)</li>
    <li>Найти кратчайший путь между двумя вершинами в невзвешенном графе за O(E)</li>
    <li>У ребер есть веса: 1 или 2, найти путь за O(E)</li>
    <li>У ребер есть веса: 0 или 1, найти путь за O(E)</li>
    <li>У ребер есть веса: 0, 1 или 2, найти путь за O(E)</li>
    <li>Покрасить граф в 2 цвета за O(E)</li>
    <li>Найти компоненты связности за O(E)</li>
    <li>Найти цикл за O(E) в орграфе</li>
    <li>Найти цикл за O(E) в неорграфе</li>
    <li>Поиск кратчайшего цикла в невзвешенном неориентированном графе за O(E<sup>2</sup>)</li>
    <li>Поиск кратчайшего цикла в невзвешенном неориентированном графе за O(VE)</li>
  </ol></li>
  <li>Поиск кратчайших путей в взвешенных графах</li>
  <ol>
    <li>Форд-Беллман за O(VE)</li>
    <li>Форд-Беллман с очередью за ~O(E)</li>
    <li>Дейкстра за O(V<sup>2</sup>)</li>
    <li>Дейкстра с кучей/set за O(ElogV)</li>
    <li>Дейкстра с деревом отрезков за O(ElogV)</li>
    <li>Дейкстра с k-ичной кучей за O(Elog<sub>V<sup>2</sup>/E</sub>V)</li>
  </ol></li>
  <li>Эйелровость</li>
  <ol>
    <li>Критерий</li>
    <li>Поиск цикла за O(E)</li>
    <li>Поиск пути за O(E)</li>
    <li>Ориентинованный случай: критерий, алгоритм</li>
  </ol></li>
</ol>
